#include <iostream>
#include<vector>
#include <string>
#include<functional>
using namespace std;

namespace dew
{
    template <class T>
    class Less
    {
    public:
        bool operator()(const T& x,const T& y)
        {
            return x < y;
        }
    };

    template <class T>
    class Greater
    {
    public:
        bool operator()(const T& x,const T& y)
        {
            return x > y;
        }
    };

    template <class T, class Container = vector<T>, class Compare = Less<T>>
    class priority_queue
    {
    public:
        priority_queue():_c(),_comp(){}
        template <class InputIterator>
        priority_queue(InputIterator first, InputIterator last);
        bool empty() const;
        size_t size() const;
        const T& top() const;
        void push(const T& x);
        void pop();
    private:
        void adjust_up(int child);
        void adjust_down(int parent);
    private:
        Container _c;
        Compare _comp;
    };

    template <class T, class Container, class Compare>
    template <class InputIterator>
    priority_queue<T,Container,Compare> :: priority_queue(InputIterator first, InputIterator last)
    :_c(),_comp()
    {
        while(first != last)
        {
            push(*first);
            first++;
        }
    }

    template <class T, class Container, class Compare>
    bool priority_queue<T,Container,Compare>::empty() const
    {
        return _c.empty();
    }

    template <class T, class Container, class Compare>
    size_t priority_queue<T,Container,Compare>::size() const
    {
        return _c.size();
    }

    template <class T, class Container, class Compare>
    const T& priority_queue<T,Container,Compare>::top() const
    {
        return _c.front();
    }

    template <class T, class Container, class Compare>
    void priority_queue<T,Container,Compare>::push(const T& x)
    {
        _c.push_back(x);
        adjust_up(_c.size() - 1);
    }

    template <class T, class Container, class Compare>
    void priority_queue<T,Container,Compare>::pop()
    {
        swap(_c.front(),_c.back());
        _c.pop_back();
        adjust_down(0);
    }

    template <class T, class Container, class Compare>
    void priority_queue<T,Container,Compare>::adjust_up(int child)
    {
        int parent = (child - 1) / 2;
        while(child > 0)
        {
            if(_comp(_c[child],_c[parent]))
            {
                swap(_c[child],_c[parent]);
                child = parent;
                parent = (child - 1) / 2;
            }
            else
            {
                break;
            }
        }

    }

    template <class T, class Container, class Compare>
    void priority_queue<T,Container,Compare>::adjust_down(int parent)
    {
        int child = parent * 2 + 1;
        while(child < _c.size())
        {
            if((child + 1 <  _c.size()) && _comp(_c[child + 1],_c[child]))
            {
                ++child;
            }
            if(_comp(_c[child],_c[parent]))
            {
                swap(_c[child],_c[parent]);
                parent = child;
                child = parent * 2 + 1;
            }
            else
             break;
        }
    }

};